package com.example.lcpractice.lc;

import com.example.lcpractice.datastructure.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 105. 从前序与中序遍历序列构造二叉树
 * <p>
 * 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
 * <p>
 * 示例 1:
 * <p>
 * 输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
 * 输出: [3,9,20,null,null,15,7]
 * 示例 2:
 * <p>
 * 输入: preorder = [-1], inorder = [-1]
 * 输出: [-1]
 * <p>
 * <p>
 * 提示:
 * <p>
 * 1 <= preorder.length <= 3000
 * inorder.length == preorder.length
 * -3000 <= preorder[i], inorder[i] <= 3000
 * preorder 和 inorder 均 无重复 元素
 * inorder 均出现在 preorder
 * preorder 保证 为二叉树的前序遍历序列
 * inorder 保证 为二叉树的中序遍历序列
 */
public class Lc105 {

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(11);

        TreeNode node2 = new TreeNode(21);
        TreeNode node3 = new TreeNode(22);
        node1.left = node2;
        node1.right = node3;

        TreeNode node4 = new TreeNode(31);
        TreeNode node5 = new TreeNode(32);
        node2.left = node4;
        node2.right = node5;
//        TreeNode node5 = new TreeNode(3);
        TreeNode node6 = new TreeNode(33);
        node3.right = node6;


        System.out.println( );
    }

    /**
     * Map
     * 键：节点的值 （题目中备注值不重复）
     * 值：树节点的在【中序遍历】中位置
     */
    private static Map<Integer, Integer> indexMap;

    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = inorder.length;
        // 构造哈希映射，帮助我们快速定位根节点
        indexMap = new HashMap<Integer, Integer>();
        //遍历中序数组
        for (int i = 0; i < n; i++) {
            indexMap.put(inorder[i], i);
        }
        //第一次递归，
        return myBuildTree(preorder, 0, n - 1, 0);
    }

    /**
     *对于任意一颗树而言，前序遍历的形式总是
     *
     * [ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
     * 即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是
     *
     * [ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
     * 只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。
     *
     * @param preorder 先序数组
     * @param preorder_left 先序子数组左边际 下一次是【先序左+1】（【先序左】是本级根节点位置）
     * @param preorder_right 先序子数组右边际 下一次是【先序左+左子树节点个数】
     * @param inorder_left 中序子数组左边际
     * @return
     */
    public static TreeNode myBuildTree(int[] preorder, int preorder_left, int preorder_right, int inorder_left) {
        if (preorder_left > preorder_right) {
            return null;
        }
        // 前序遍历中的第一个节点就是根节点
        int preorder_root = preorder_left;
        // 因为节点val不重复，根据前序遍历数组中根节点的值获取中序遍历数组中位置
        int inorder_root = indexMap.get(preorder[preorder_root]);
        // 先把根节点建立出来
        TreeNode root = new TreeNode(preorder[preorder_root]);
        // 得到左子树中的节点数目【中序遍历根节点位置-中序遍历左起点位置】
        int size_left_subtree = inorder_root - inorder_left;
        // 递归地构造左子树，并连接到根节点 // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
        root.left = myBuildTree(preorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left);
        // 递归地构造右子树，并连接到根节点
        // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
        root.right = myBuildTree(preorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1);
        return root;
    }




}
